{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Super Pow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: superPow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #超级次方"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你的任务是计算 <code>a<sup>b</sup></code> 对 <code>1337</code> 取模，<code>a</code> 是一个正整数，<code>b</code> 是一个非常大的正整数且会以数组形式给出。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 2, b = [3]\n",
    "<strong>输出：</strong>8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 2, b = [1,0]\n",
    "<strong>输出：</strong>1024\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 1, b = [4,3,3,8,5,2]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>a = 2147483647, b = [2,0,0]\n",
    "<strong>输出：</strong>1198\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= a <= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>1 <= b.length <= 2000</code></li>\n",
    "\t<li><code>0 <= b[i] <= 9</code></li>\n",
    "\t<li><code>b</code> 不含前导 0</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [super-pow](https://leetcode.cn/problems/super-pow/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [super-pow](https://leetcode.cn/problems/super-pow/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['2\\n[3]', '2\\n[1,0]', '1\\n[4,3,3,8,5,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        # 秦九韶算法 看第50题\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for e in b:\n",
    "            ans = pow(ans, 10, MOD) * pow(a, e, MOD) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def myPow(self, a, n):\n",
    "        if n == 0: return 1\n",
    "        if n % 2 == 1: \n",
    "            return (self.myPow(a, n - 1) * a) % 1337 \n",
    "        else:\n",
    "            sub = self.myPow(a, n // 2)\n",
    "            return (sub * sub) % 1337\n",
    "       \n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b: return 1\n",
    "        last = b.pop()\n",
    "        part1 = self.myPow(a, last)\n",
    "        part2 = self.myPow(self.superPow(a, b), 10)\n",
    "        return (part1 * part2) % 1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#\n",
    "# @lc app=leetcode.cn id=372 lang=python3\n",
    "#\n",
    "# [372] 超级次方\n",
    "#\n",
    "\n",
    "# @lc code=start\n",
    "from typing import List\n",
    "\n",
    "# 法1：记 a = mx + n, 将 a^b -> n^b, 然后对b分奇偶数二分求余 效率：5.68%\n",
    "# 可以用尾递归优化吗？\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        X = 1337\n",
    "        n = a % X\n",
    "        number = 0\n",
    "        for v in b:\n",
    "            number = number * 10 + v\n",
    "            \n",
    "        def getNumber(a, b):\n",
    "            if b == 1:\n",
    "                return a\n",
    "            if b % 2:\n",
    "                #return ((getNumber(a, b // 2))** 2 * a ) % X\n",
    "                return ((getNumber(a, b // 2) % X)** 2 * a ) % X\n",
    "            else:\n",
    "                return ((getNumber(a, b // 2) % X) ** 2 ) % X\n",
    "        \n",
    "        return getNumber(n, number)\n",
    "\n",
    "\n",
    "# 将b递归分解成两部分，分别求对X = 1337 的模，然后结果相乘再求模\n",
    "# b 不一定要 b/2这样分解，可以按照对10求余和取模分成两部分\n",
    "# (a^b) % X = (n^b)%X\n",
    "\n",
    "# class Solution:\n",
    "#     def superPow(self, a: int, b: List[int]) -> int:\n",
    "#         X = 1337\n",
    "#         a = a % X\n",
    "#         def smallPow(a, k):\n",
    "#             res = 1\n",
    "#             for i in range(k):\n",
    "#                 res = (res * a) % X\n",
    "#             return res\n",
    "#         def divideList(a, b):\n",
    "#             if not b:\n",
    "#                 return 1\n",
    "#             last = b.pop()\n",
    "#             part1 = smallPow(a, last)\n",
    "#             #part2 = divideList(a, b) ** 10\n",
    "#             part2 = smallPow(divideList(a, b), 10)\n",
    "#             return (part1 * part2) % X\n",
    "#         return divideList(a, b)\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        X = 1337\n",
    "        a = a % X\n",
    "        def smallPow(a, k):\n",
    "            res = 1\n",
    "            for i in range(k):\n",
    "                res = (res * a) % X\n",
    "            return res\n",
    "        def divideList(a, b):\n",
    "            if not b:\n",
    "                return 1\n",
    "            last = b.pop()\n",
    "            part1 = a ** last % X\n",
    "            #part2 = divideList(a, b) ** 10\n",
    "            part2 = (divideList(a, b) ** 10) % X\n",
    "            return (part1 * part2) % X\n",
    "        return divideList(a, b)         \n",
    "# @lc code=end\n",
    "obj = Solution()\n",
    "a = 2147483647\n",
    "b = [2,0,0]\n",
    "\n",
    "# a = 2\n",
    "# b = [1, 0]\n",
    "res = obj.superPow(a,b)\n",
    "print(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b) == 0:\n",
    "            return 1\n",
    "        k = b.pop()\n",
    "        part1 = self.mypow(a, k)\n",
    "        part2 = self.mypow(self.superPow(a, b), 10)\n",
    "        return part1 * part2 % 1337\n",
    "\n",
    "        \n",
    "    def mypow(self, a, k):\n",
    "        if k == 0:\n",
    "            return 1\n",
    "        if k % 2 == 1:\n",
    "            return a * self.mypow(a, k-1) % 1337\n",
    "        else:\n",
    "            return ((self.mypow(a, k // 2)) * (self.mypow(a, k // 2))) % 1337\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        M = 1337\n",
    "        m = a % M\n",
    "        \n",
    "        def myPow(x: int, n: int) -> int:\n",
    "            ans = 1\n",
    "            base = x\n",
    "            while n > 0:\n",
    "                if n & 1:\n",
    "                    ans = (ans * base) % M\n",
    "                base *= base\n",
    "                n >>= 1\n",
    "            return ans\n",
    "        \n",
    "        ans = 1\n",
    "        for n in b[-1::-1]:\n",
    "            ans = (ans * myPow(m, n)) % M\n",
    "            m = myPow(m, 10)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        num=0\n",
    "        for i in b:\n",
    "            num=num*10+i\n",
    "        return pow(a,num,1337)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "\n",
    "class Solution:\n",
    "    mod = 1337\n",
    "    def power(self, a, b):\n",
    "        ans = 1\n",
    "        carry = a\n",
    "        while b != 0:\n",
    "            if b & 1:\n",
    "                ans = (ans * carry) % self.mod\n",
    "            carry *= carry\n",
    "            b >>= 1\n",
    "        return ans\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        ans = 1\n",
    "        carry = a\n",
    "        for ele in b[::-1]:\n",
    "            ans = (ans * self.power(carry, ele)) % self.mod\n",
    "            carry = self.power(carry, 10)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "\n",
    "        def pows(x: int, y: int) -> int:\n",
    "\n",
    "            c = x\n",
    "            ans = 1\n",
    "            while y > 0:\n",
    "                if y & 1:\n",
    "                    ans *= c\n",
    "                    ans %= 1337\n",
    "\n",
    "                c *= c\n",
    "                y >>= 1\n",
    "            return ans\n",
    "\n",
    "        k = 1\n",
    "        res = 1\n",
    "        for o in b:\n",
    "            res = pows(a, o) * pows(res, 10)\n",
    "            res %= 1337\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        bb,r=0,1\n",
    "        for n in b:bb=bb*10+n\n",
    "        while bb:\n",
    "            if bb&1:r=r*a%1337\n",
    "            a,bb=a*a%1337,bb>>1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if b == [0]: return 1\n",
    "        a %= 1337\n",
    "        base = a\n",
    "        vals, vis = [], set()\n",
    "        for i in range(1337):\n",
    "            if a in vis:\n",
    "                break\n",
    "            vals.append(a)\n",
    "            vis.add(a)\n",
    "            a = (a * base) % 1337\n",
    "        k = len(vals)\n",
    "        i = 0\n",
    "        for x in b:\n",
    "            i = (i * 10 + x) % k\n",
    "        return vals[(i + k - 1) % k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for e in reversed(b):\n",
    "            ans = ans * pow(a, e, MOD) % MOD\n",
    "            a = pow(a, 10, MOD)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if a == 1:\n",
    "            return 1\n",
    "        res = 1\n",
    "        n = len(b)\n",
    "        for i in range(n):\n",
    "            res = self.myPow(a, b[i]) * self.myPow(res, 10) % 1337\n",
    "        return res\n",
    "    def myPow(self, a, r):\n",
    "        res = 1\n",
    "        a = a % 1337\n",
    "        for _ in range(r):\n",
    "            res *= a\n",
    "            res %= 1337\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for i in reversed(b):\n",
    "            ans = ans * pow(a, i, MOD) % MOD\n",
    "            a = pow(a, 10, MOD)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        res = 1\n",
    "        for e in reversed(b):\n",
    "            res = res*pow(a, e, 1337) % 1337\n",
    "            a = pow(a, 10, 1337)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if a in [0, 1]:\n",
    "            return a\n",
    "        base = a\n",
    "        base_base = a ** 10 % 1337\n",
    "        res = []\n",
    "        while len(b) > 0:\n",
    "            tmp = b.pop()\n",
    "            x = base ** tmp % 1337\n",
    "            res.append(x)\n",
    "            base = base ** 10 % 1337\n",
    "            #print(tmp, base, x, res)\n",
    "        ans = 1\n",
    "        \n",
    "        for i in res:\n",
    "            ans = (ans * i) % 1337\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        mod=1337\n",
    "        def quickPow(x,n):\n",
    "            ans=1\n",
    "            while n:\n",
    "                if n&1>0:\n",
    "                    ans=(ans*x)%mod  # 对 ans 取模\n",
    "                x=(x*x)%mod          # 先对 x 进行取模，再进行乘法运算\n",
    "                n>>=1\n",
    "            return ans\n",
    "\n",
    "        res=1\n",
    "        for e in reversed(b):\n",
    "            res=(res*quickPow(a,e))%mod  # 对每一步的乘积进行取模\n",
    "            a=quickPow(a,10)%mod\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        return pow(a, int(\"\".join(map(str, b))), 1337)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        res = 1\n",
    "        exp = \"\"\n",
    "        for n in b:\n",
    "            exp+=str(n)\n",
    "        b = int(exp)\n",
    "        binary_exponent = bin(b)[2:]\n",
    "\n",
    "        # 1337也就是a^b mod n中的n\n",
    "        for bit in binary_exponent:\n",
    "            res = (res ** 2) % 1337\n",
    "            if bit == '1':\n",
    "                res = (res * a) % 1337\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD=1337\n",
    "        res=1\n",
    "        for e in reversed(b):\n",
    "            res=res*pow(a,e,MOD)%MOD\n",
    "            a=pow(a,10,MOD)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        res = 1\n",
    "        for bi in b[::-1]:\n",
    "            res = res * pow(a, bi, MOD) % MOD \n",
    "            a = pow(a, 10, MOD)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for e in reversed(b):\n",
    "            ans = ans*pow(a,e,MOD) % MOD\n",
    "            a = pow(a,10,MOD)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if a == 1:\n",
    "            return 1\n",
    "        res = 1\n",
    "        n = len(b)\n",
    "        for i in range(n):\n",
    "            res = self.myPow(a, b[i]) * self.myPow(res, 10) % 1337\n",
    "        return res\n",
    "    def myPow(self, a, r):\n",
    "        if r == 0:\n",
    "            return 1\n",
    "        a = a % 1337\n",
    "        if r % 2 == 1:\n",
    "            return (self.myPow(a, r - 1) * a) % 1337\n",
    "        else:\n",
    "            return self.myPow(a, r//2) ** 2 % 1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "\n",
    "        base = a % 1337\n",
    "        result = 1\n",
    "        # 快速幂:对指数数组 b 进行处理。\n",
    "        # 每一步中:先将 result 进行 10 的幂次运算，再与 base 的 digit 次幂进行运算，同时取模。\n",
    "        for digit in b:\n",
    "            result = (pow(result, 10, 1337) * pow(base, digit, 1337)) % 1337\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        ans = 1\n",
    "        for each in b:\n",
    "            ans = pow(ans, 10, 1337) * pow(a, each, 1337) % 1337\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for e in reversed(b):\n",
    "            ans = ans * pow(a, e, MOD) % MOD\n",
    "            a = pow(a, 10, MOD)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        num = 0\n",
    "        for digit in b:\n",
    "            num = num * 10 + digit\n",
    "        return pow(a, num, 1337) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        '''\n",
    "        # a * b % m == (a % m) * (b % m) % m\n",
    "        # pow(a, b) % m == pow(a % m, b) % m\n",
    "        # pow(a, b * c) == pow(pow(a, b), c)\n",
    "        # pow(a, b) % m == pow(a, b, m) \n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for n in b:\n",
    "            ans = pow(ans, 10, MOD) * pow(a, n, MOD) % MOD\n",
    "        return ans\n",
    "        '''\n",
    "        #return pow(a, int(''.join([str(_) for _ in b])), 1337)\n",
    "        return pow(a, int(''.join(map(str, b))), 1337)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        n=len(b)\n",
    "        ans=1\n",
    "        mod=1337\n",
    "        for i in range(n-1,-1,-1):\n",
    "            e=b[i]\n",
    "            ans=ans*pow(a,e,mod)%mod\n",
    "            a=pow(a,10)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        d=1337\n",
    "        a=a%d\n",
    "        if a==0:\n",
    "            return 0\n",
    "        r=a\n",
    "        all_r=[1,a]\n",
    "        while True:\n",
    "            r=(r*a)%d\n",
    "            if r==a:\n",
    "                break\n",
    "            all_r.append(r)\n",
    "        all_r[0]=all_r[-1]\n",
    "        n=len(all_r)-1\n",
    "        print('AAAA',all_r)\n",
    "        b_value=0\n",
    "        for c in b:\n",
    "            b_value=10*b_value+c\n",
    "            b_value=b_value%n\n",
    "\n",
    "        return all_r[b_value]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        a1=a%7\n",
    "        a2=a%191\n",
    "        if a1==0:\n",
    "            k1=0\n",
    "        else:\n",
    "            ans1=[1]\n",
    "            a3=a1\n",
    "            for i in range(5):\n",
    "                ans1.append(a3)\n",
    "                a3=(a3*a1)%7\n",
    "        if a2==0:\n",
    "            k2=0\n",
    "        else:\n",
    "            ans2=[1]\n",
    "            a4=a2\n",
    "            for i in range(189):\n",
    "                ans2.append(a4)\n",
    "                a4=(a4*a2)%191\n",
    "        c=[str(i) for i in b]\n",
    "        e=int(''.join(c))\n",
    "        if a1!=0:\n",
    "            k1=ans1[e%6]\n",
    "        if a2!=0:\n",
    "            k2=ans2[e%190]\n",
    "        for i in range(10):\n",
    "            if (191*i+k2-k1)%7==0:\n",
    "                return 191*i+k2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        a=a%1337\n",
    "        n=len(b)\n",
    "        res=1\n",
    "        print(a)\n",
    "        buf=a\n",
    "        for i in range(n-1,-1,-1):\n",
    "            \n",
    "            m=pow(buf,b[i],1337)\n",
    "            res=int(res*m)%1337\n",
    "            buf=int(pow(buf,10,1337))%1337\n",
    "            print(m,res,buf)\n",
    "        print(603**2%1337)\n",
    "        print(pow(932,200,1337))\n",
    "        print(pow(932,100,1337)**2%1337)\n",
    "        print(pow(932,100,1337),pow(pow(932,10,1337),10,1337))\n",
    "        return res\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "\n",
    "        def mypow(a, b):\n",
    "            if len(b) == 0:\n",
    "                return 1\n",
    "            last_num = b.pop()\n",
    "            part1 = (a ** last_num) % 1337\n",
    "            part2 = mypow(a, b)**10 % 1337\n",
    "            print(last_num, part1, part2)\n",
    "            return (part1*part2) % 1337\n",
    "        \n",
    "        return mypow(a, b)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        a = a % 1337\n",
    "        n = len(b)\n",
    "        l = [0]*n\n",
    "        l[0] = a\n",
    "        for i in range(1,n):\n",
    "            l[i] = pow(l[i-1], 10, mod = 1337)\n",
    "        res = 1\n",
    "        print(l)\n",
    "        for i in range(n):\n",
    "            res = (res * pow(l[i], b[n-i-1], mod = 1337)) % 1337\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        base = 1337\n",
    "        def mypow(a,k):\n",
    "            return ((a%base)**k)%base\n",
    "        if len(b)==0: return 1\n",
    "        last = b.pop()\n",
    "        left = mypow(a,last)\n",
    "        right = mypow(self.superPow(a,b),10)\n",
    "        return (left*right)%base\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        d1={}\n",
    "        d2=[]\n",
    "        a=a%1337\n",
    "        num=reduce(lambda x,y:10*x+y,b,0)\n",
    "        def dfs(aa,ab,i):\n",
    "            a=ab%1337\n",
    "            if i>=num:\n",
    "                return a\n",
    "            if a not in d1.keys():\n",
    "                d1[a]=i\n",
    "                d2.append(a)\n",
    "                return dfs(aa,a*aa,i+1)\n",
    "            else:\n",
    "                return d2[(num%(i-1))-1]\n",
    "                #return i,d2\n",
    "                \n",
    "        return dfs(a,a,1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        base = 1337\n",
    "        def compute(a: int, n: int) -> int:\n",
    "            \"\"\"计算 a 的 k 次方然后与 base 求模的结果\"\"\"\n",
    "            a %= base\n",
    "            res = 1\n",
    "            for i in range(n):\n",
    "                res *= a\n",
    "                res %= base\n",
    "            \n",
    "            return res\n",
    "\n",
    "        # base case: b=0, a^0=1\n",
    "        if not b:\n",
    "            return 1\n",
    "        last = b.pop()\n",
    "        p1 = compute(a, last)\n",
    "        p2 = compute(self.superPow(a, b), 10)\n",
    "        return p1 * p2 % base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD=1337\n",
    "        #return pow(a, int(\"\".join(map(str,b))), 1337)\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD\n",
    "        \n",
    "        def quickPow(x, y):\n",
    "            ans = 1\n",
    "            x %= MOD\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    ans = ans * x % MOD\n",
    "                x = x * x % MOD\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        \n",
    "        a %= MOD\n",
    "        return dfs(len(b) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        mod = 1337\n",
    "        def qpow(a , n):\n",
    "            ans = 1\n",
    "            a = a % mod\n",
    "            while(n):\n",
    "                if n & 1:\n",
    "                    ans = ans * a % mod\n",
    "                a = a * a % mod \n",
    "                n >>= 1\n",
    "            return ans\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            else:\n",
    "                return qpow(dfs(i-1), 10) * qpow(a, b[i]) % mod\n",
    "        a = a % mod\n",
    "        return dfs(len(b) - 1) \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        d1={}\n",
    "        d2=[]\n",
    "        a=a%1337\n",
    "        num=reduce(lambda x,y:10*x+y,b,0)\n",
    "        def dfs(aa,ab,i):\n",
    "            a=ab%1337\n",
    "            if i>=num:\n",
    "                return a\n",
    "            if a not in d1.keys():\n",
    "                d1[a]=i\n",
    "                d2.append(a)\n",
    "                return dfs(aa,a*aa,i+1)\n",
    "            else:\n",
    "                return d2[(num%(i-1))-1]\n",
    "                #return i,d2\n",
    "                \n",
    "        return dfs(a,a,1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD\n",
    "        \n",
    "        def quickPow(x, y):\n",
    "            ans = 1\n",
    "            x %= MOD\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    ans = ans * x % MOD\n",
    "                x = x * x % MOD\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        MOD = 1337\n",
    "        # a %= MOD\n",
    "        return dfs(len(b) - 1)\n",
    "\n",
    "# class Solution {\n",
    "#     int MOD = 1337;\n",
    "#     public int superPow(int a, int[] b) {\n",
    "#         return dfs(a, b, b.length - 1);\n",
    "#     }\n",
    "#     int dfs(int a, int[] b, int u) {\n",
    "#         if (u == -1) return 1;\n",
    "#         return qpow(dfs(a, b, u - 1), 10) * qpow(a, b[u]) % MOD;\n",
    "#     }\n",
    "#     int qpow(int a, int b) {\n",
    "#         int ans = 1;\n",
    "#         a %= MOD;\n",
    "#         while (b != 0) {\n",
    "#             if ((b & 1) != 0) ans = ans * a % MOD;\n",
    "#             a = a * a % MOD;\n",
    "#             b >>= 1;\n",
    "#         }\n",
    "#         return ans;\n",
    "#     }\n",
    "# }\n",
    "\n",
    "# 作者：AC_OIer\n",
    "# 链接：https://leetcode-cn.com/problems/super-pow/solution/gong-shui-san-xie-di-gui-kuai-su-mi-ying-yx1j/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        def mypow(base, k):\n",
    "            if k == 0:\n",
    "                return 1\n",
    "            last = mypow(base, k // 2) % MOD\n",
    "            if k % 2 == 0:\n",
    "                return (last ** 2) % MOD\n",
    "            else:\n",
    "                return ((last ** 2) * base) % MOD\n",
    "        \n",
    "        if not b:\n",
    "            return 1\n",
    "        last_num = b.pop()\n",
    "        last_power = mypow(a, last_num) % MOD\n",
    "        next_power = mypow(self.superPow(a, b), 10) % MOD\n",
    "        return  (last_power * next_power) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1337\n",
    "# (x*y) % z = (x%z) * (y*z) % z\n",
    "# x ** (10*a+b) * z = \n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        a = a % MOD\n",
    "        def quickPow(x: int, y: int):\n",
    "            # x ** y(1010) % MOD\n",
    "            x = x % MOD\n",
    "            ans = 1\n",
    "            while(y):\n",
    "                if (y & 1):\n",
    "                    ans = (ans * x) % MOD\n",
    "                x = (x * x) % MOD\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        \n",
    "        def dfs(i):\n",
    "            # a的(b的前i位)次方 % MOD = (a的(b的前i-1位)次方)的10次方 % MOD * a的b的第i位 % MOD\n",
    "            if i == 0:\n",
    "                return 1\n",
    "            return quickPow(dfs(i-1), 10) * quickPow(a, b[i-1]) % MOD\n",
    "        return dfs(len(b))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD\n",
    "        \n",
    "        def quickPow(x, y):\n",
    "            ans = 1\n",
    "            x %= MOD\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    ans = ans * x % MOD\n",
    "                x = x * x % MOD\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        \n",
    "        a %= MOD\n",
    "        return dfs(len(b) - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        base=1337\n",
    "        def mypow(a,k):\n",
    "            if k == 0:return 1\n",
    "            a %= base \n",
    "            if k%2==1:\n",
    "                return (a*mypow(a,k-1))%base\n",
    "            else:\n",
    "                sub = mypow(a,k/2)\n",
    "                return sub*sub%base\n",
    "\n",
    "        if not b: return 1\n",
    "        last = b.pop()\n",
    "        part1 = mypow(a,last)\n",
    "        part2 = mypow(self.superPow(a,b),10)\n",
    "        return part1*part2%base\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "\n",
    "        base=1337\n",
    "\n",
    "        def mypow(a,k):\n",
    "            # a%=base\n",
    "            # res=1\n",
    "            # for _ in range(k):\n",
    "            #     res*=a\n",
    "            #     res%=base\n",
    "            # return res\n",
    "            a%=base\n",
    "            if k==0:\n",
    "                return 1\n",
    "            if k%2==0:\n",
    "                return mypow(a,k//2)*mypow(a,k//2)%base\n",
    "            else:\n",
    "                return a*mypow(a,k-1)%base\n",
    "        \n",
    "        k=b.pop(-1)\n",
    "        p1=mypow(a,k)\n",
    "        p2=mypow(self.superPow(a,b),10)\n",
    "        return p1*p2%base\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = self.mypowmod(a,tmp)\n",
    "        part2 = self.mypowmod(self.superPow(a,b),10)\n",
    "        return (part1*part2)%1337\n",
    "\n",
    "\n",
    "    def mypowmod(self, a, k):\n",
    "        a %= 1337\n",
    "        res = 1\n",
    "        while k > 0:\n",
    "            if k % 2 == 1:\n",
    "                res = (res * a) % 1337\n",
    "            a = (a * a) % 1337\n",
    "            k //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        base = 1337\n",
    "        def mypow(a,k):\n",
    "            if k==0:\n",
    "                return 1\n",
    "            a %= base\n",
    "            res = 1\n",
    "            if k%2==1:\n",
    "                return (a*mypow(a,k-1))%base\n",
    "            else:\n",
    "                return (mypow(a,k//2)**2)%base\n",
    "            return res\n",
    "        if not b:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = mypow(a,tmp)\n",
    "        part2 = mypow(self.superPow(a,b),10)\n",
    "        return (part1*part2)%base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(x, n):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if n == 1:\n",
    "                return x % 1337\n",
    "            half = help(x, n//2)\n",
    "            return half*half*(x % 1337 if n & 1 else 1) % 1337\n",
    "\n",
    "        res = 1\n",
    "        for num in b:\n",
    "            res = help(res, 10)*help(a, num) % 1337\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def help(x, n):\n",
    "            if n == 0:\n",
    "                return 1\n",
    "            if n == 1:\n",
    "                return x % 1337\n",
    "            half = help(x, n//2)\n",
    "            return half*half*(x % 1337 if n & 1 else 1) % 1337\n",
    "\n",
    "        res = 1\n",
    "        for num in b:\n",
    "            res = help(res, 10)*help(a, num) % 1337\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "        l = b.pop()\n",
    "\n",
    "        l1 = (a**l)%1337\n",
    "\n",
    "        l2=(self.superPow(a,b)**10)%1337\n",
    "\n",
    "        return (l1*l2)%1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        index = 0\n",
    "        for i in b:\n",
    "            index = 10 * index + i\n",
    "        return self.recur(a, index)\n",
    "\n",
    "    def recur(self, a: int, index: int) -> int:\n",
    "        if a <= 1:\n",
    "            return a\n",
    "        tmp = 1\n",
    "        for i in range(1, index + 1):\n",
    "            tmp *= a\n",
    "            if tmp > 1337:\n",
    "                break\n",
    "        if tmp <= 1337:\n",
    "            return tmp % 1337\n",
    "        return ((a ** (index % i)) * self.recur(tmp % 1337, index // i)) % 1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def mypow(self,a: int, k: int,MOD) -> int:\n",
    "        a = a % MOD\n",
    "        res = 1\n",
    "        while k >0:\n",
    "            if k & 1:\n",
    "                res = ((res % MOD) * a)  % MOD \n",
    "            a = (a * a ) % MOD\n",
    "            k = k // 2\n",
    "        return res\n",
    "            \n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        base = 1337\n",
    "        # i = b.pop()\n",
    "        while b:\n",
    "            i = b.pop()\n",
    "            part1 = self.mypow(a,i,base)\n",
    "            part2 = self.mypow(self.superPow(a,b),10,base)\n",
    "            return (part1 % base * part2 % base) % base\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        self.base = 1337\n",
    "        MOD = 1337\n",
    "        ans = 1\n",
    "        for e in reversed(b):\n",
    "            ans = ans * self.mypow(a, e, MOD) % MOD\n",
    "            a = self.mypow(a, 10, MOD)\n",
    "        return ans\n",
    "\n",
    "\n",
    "    # def superPow(self,a: int, b: List[int]) -> int:\n",
    "    #     # 递归的 base case\n",
    "    #     self.base = 1337\n",
    "\n",
    "    #     if not b:\n",
    "    #         return 1\n",
    "    #     # 取出最后一个数\n",
    "    #     last = b.pop()\n",
    "    #     # 将原问题化简，缩小规模递归求解\n",
    "    #     # part1 = self.mypow(a, last)\n",
    "    #     # part2 = self.mypow(self.superPow(a, b), 10)\n",
    "    #     # 合并出结果\n",
    "    #     now = self.mypow(a, last)\n",
    "    #     res = now\n",
    "    #     tmp_l = last\n",
    "    #     while b:\n",
    "    #         tmp = now\n",
    "    #         last = b.pop()\n",
    "    #         res = res * self.mypow(res, last) % self.base\n",
    "    #         last = self.mypow(last, 10)\n",
    "\n",
    "    #         # now = self.mypow(a, last) *self.mypow(a,10)\n",
    "    #         # res = (tmp % self.base ) * (now % self.base) % self.base\n",
    "\n",
    "    #     return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        self.MOD = 1337\n",
    "        return self.dfs(a, b, len(b) - 1)\n",
    "    \n",
    "    def dfs(self, a, b, u):\n",
    "        if u == -1:\n",
    "            return 1\n",
    "        return self.qmi(self.dfs(a, b, u - 1), 10) * self.qmi(a, b[u]) % self.MOD\n",
    "    \n",
    "    def qmi(self, a, b):\n",
    "        res = 1\n",
    "        a = a % self.MOD\n",
    "        while b != 0:\n",
    "            if b & 1 != 0:\n",
    "                res = res * a % self.MOD\n",
    "            a = a * a % self.MOD\n",
    "            b >>= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\r\n",
    "        \r\n",
    "        a %= 1337\r\n",
    "        r = a\r\n",
    "        n = len(b)\r\n",
    "        x = 0\r\n",
    "        for i, num in enumerate(b):\r\n",
    "            x += num * (10 ** (n - i - 1))\r\n",
    "        lis = []\r\n",
    "        while x > 1:\r\n",
    "            lis.append(x)\r\n",
    "            x //= 2\r\n",
    "        for i in range(len(lis) - 1, -1, -1):\r\n",
    "            if lis[i] % 2 == 0:\r\n",
    "                a *= a\r\n",
    "            else:\r\n",
    "                a = a * a * r\r\n",
    "            a %= 1337\r\n",
    "        return a\r\n",
    "        \r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = self.mypowmod(a,tmp)\n",
    "        part2 = self.mypowmod(self.superPow(a,b),10)\n",
    "        return (part1*part2)%1337\n",
    "\n",
    "    def mypowmod(self,a,k)-> int:\n",
    "        a = a%1337\n",
    "        res = 1\n",
    "        for i in range(k):\n",
    "            res*=a\n",
    "            res%=1337\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b: return 1\n",
    "        tmp = b.pop()\n",
    "        return (((self.superPow(a, b)) ** 10) % 1337 * \\\n",
    "                (a ** tmp) % 1337 ) % 1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b) == 0:\n",
    "            return 1\n",
    "        last = b.pop()\n",
    "        res = (self.myPow(a, last) * self.myPow(self.superPow(a, b), 10)) % 1337\n",
    "        return res\n",
    "    \n",
    "    # 计算 a 的 k 次方然后与 base 求模的结果\n",
    "    def myPow(self, a, k):\n",
    "        a = a % 1337\n",
    "        res = 1\n",
    "        for i in range(k):\n",
    "            res = res * a\n",
    "            res = res % 1337\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        a = a%1337\n",
    "        b0 = b.pop()\n",
    "        anew,anow=1,1\n",
    "        for i in range(10):\n",
    "            if i==b0:\n",
    "                anow=anew\n",
    "            anew = (anew*a)%1337\n",
    "        return (self.superPow(anew,b)*anow)%1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 如何处理 mod 运算?\n",
    "# 模运算的技巧：(a * b) % k = (a % k) * (b % k) % k\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    mod = 1337  # 声明一个类变量,表示取模数\n",
    "\n",
    "    # 计算a的k次方，参考leetcode 50题, 这里是计算a的k次方，然后对1337取模的结果\n",
    "    def myPow(self, a: int, k: int):\n",
    "        a %= self.mod\n",
    "        res = 1\n",
    "        for i in range(k):\n",
    "            res *= a\n",
    "            res %= self.mod\n",
    "        return res\n",
    "\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "\n",
    "        last = b.pop()  # 取出 b 数组的最后一个元素\n",
    "        part1 = self.myPow(a, last)  # 计算 a 的 last 次方\n",
    "        part2 = self.myPow(self.superPow(a, b), 10)  # 递归计算 superPow(a, b[:len(b)-1]) 的 10 次方\n",
    "\n",
    "        return (part1 * part2) % self.mod  # 返回结果，每次都对结果求模"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = self.mypowmod(a,tmp)\n",
    "        part2 = self.mypowmod(self.superPow(a,b),10)\n",
    "        return (part1*part2)%1337\n",
    "\n",
    "    def mypowmod(self, a, k):\n",
    "        if k==0:\n",
    "            return 1\n",
    "        if k==1:\n",
    "            return a%1337\n",
    "        if k%2==0:\n",
    "            tmp = self.mypowmod(a,k//2)\n",
    "            return (tmp*tmp)%1337\n",
    "        else:\n",
    "            tmp = self.mypowmod(a,k-1)\n",
    "            return (tmp*(a%1337))%1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = self.mypowmod(a,tmp)\n",
    "        part2 = self.mypowmod(self.superPow(a,b),10)\n",
    "        return (part1*part2)%1337\n",
    "\n",
    "    def mypowmod(self, a, k):\n",
    "        if k==0:\n",
    "            return 1\n",
    "        if k==1:\n",
    "            return a%1337\n",
    "        if k%2==0:\n",
    "            tmp = self.mypowmod(a,k//2)\n",
    "            return (tmp*tmp)%1337\n",
    "        else:\n",
    "            tmp = self.mypowmod(a,k-1)\n",
    "            return (tmp*(a%1337))%1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.base = 1337\n",
    "    ###求a的b次方，并对base做余数的函数\n",
    "    def mypow_mod(self,a,b):\n",
    "        ##a的0次方=1\n",
    "        if b == 0:\n",
    "            return 1\n",
    "        \n",
    "        a %= self.base\n",
    "        ##幂次为奇数的情况\n",
    "        if b%2 == 1:\n",
    "            return (a*self.mypow_mod(a,b-1))%self.base\n",
    "        ##幂次为偶数的情况\n",
    "        else:\n",
    "            sub = self.mypow_mod(a,b//2)\n",
    "            return (sub*sub)%self.base\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if b == []:\n",
    "            return 1\n",
    "        p = b.pop()\n",
    "        part1 = self.mypow_mod(a,p)\n",
    "        part2 = self.mypow_mod(self.superPow(a,b),10)\n",
    "        return (part1*part2)%self.base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.base = 1337\n",
    "\n",
    "    # 计算 a 的 k 次方然后与 base 求模的结果\n",
    "    def mypow(self, a: int, k: int) -> int:\n",
    "        # 对因子求模\n",
    "        a %= self.base\n",
    "        res = 1\n",
    "        for _ in range(k):\n",
    "            # 这里有乘法，是潜在的溢出点\n",
    "            res = (res * a) % self.base\n",
    "        return res\n",
    "\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "        last = b.pop()\n",
    "\n",
    "        part1 = self.mypow(a, last)\n",
    "        part2 = self.mypow(self.superPow(a, b), 10)\n",
    "        # 每次乘法都要求模\n",
    "        return (part1 * part2) % self.base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.base = 1337\n",
    "\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "\n",
    "        last = b.pop()\n",
    "        part1 = self.myPow(a, last)\n",
    "        part2 = self.myPow(self.superPow(a, b), 10)\n",
    "\n",
    "        return (part1 * part2) % self.base\n",
    "\n",
    "    def myPow(self, x, n):\n",
    "        x %= self.base\n",
    "        res = 1\n",
    "        for _ in range(n):\n",
    "            res *= x\n",
    "            res %= self.base\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        def mypow(a,k):\n",
    "            res = 1\n",
    "            if k==0: return 1\n",
    "            for i in range(k):\n",
    "                res *= a\n",
    "                res %= 1337\n",
    "            return res\n",
    "        if len(b) == 0 or a == 1: return 1\n",
    "        var=b.pop()\n",
    "        num1=mypow(a,var)\n",
    "        num2=mypow(self.superPow(a,b),10)\n",
    "        return (num1*num2)%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b: return 1\n",
    "        tmp = b.pop()\n",
    "        return (((self.superPow(a, b)) ** 10) % 1337 * \\\n",
    "                (a ** tmp) % 1337 ) % 1337"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        self.base = 1337\n",
    "        if not b:\n",
    "            return 1\n",
    "        last = b.pop()\n",
    "        p1= self.mypower(a, last)\n",
    "        p2 = self.mypower(self.superPow(a, b), 10)\n",
    "        return (p1*p2)%self.base\n",
    "\n",
    "    def mypower(self, a, k):\n",
    "        res = 1\n",
    "        a %= self.base\n",
    "        for i in range(k):\n",
    "            res *= a\n",
    "            res %= self.base\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 如何处理 mod 运算?\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    mod = 1337  # 声明一个类变量,表示取模数\n",
    "\n",
    "    # 计算a的k次方，参考leetcode 50题, 这里是计算a的k次方，然后对1337取模的结果\n",
    "    def myPow(self, a: int, k: int):\n",
    "        a %= self.mod\n",
    "        res = 1\n",
    "        for i in range(k):\n",
    "            res *= a\n",
    "            res %= self.mod\n",
    "        return res\n",
    "\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if not b:\n",
    "            return 1\n",
    "\n",
    "        last = b.pop()  # 取出 b 数组的最后一个元素\n",
    "        part1 = self.myPow(a, last)  # 计算 a 的 last 次方\n",
    "        part2 = self.myPow(self.superPow(a, b), 10)  # 递归计算 superPow(a, b[:len(b)-1]) 的 10 次方\n",
    "\n",
    "        return (part1 * part2) % self.mod  # 返回结果，每次都对结果求模"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1337\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD\n",
    "        \n",
    "        def quickPow(x, y):\n",
    "            ans = 1\n",
    "            x %= MOD\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    ans = ans * x % MOD\n",
    "                x = x * x % MOD\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        \n",
    "        a %= MOD\n",
    "        return dfs(len(b) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        def mypow(a,k):\n",
    "            res = a\n",
    "            if k==0: return 1\n",
    "            res %= 1337\n",
    "            for i in range(k-1):\n",
    "                res *= a\n",
    "                res %= 1337\n",
    "            return res\n",
    "        if len(b)==0 or a==1: return 1\n",
    "        var=b.pop()\n",
    "        num1=mypow(a,var)\n",
    "        num2=mypow(self.superPow(a,b),10)\n",
    "        return (num1*num2)%1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b)==0:\n",
    "            return 1\n",
    "        tmp = b.pop()\n",
    "        part1 = self.mypowmod(a,tmp)\n",
    "        part2 = self.mypowmod(self.superPow(a,b),10)\n",
    "        print(part1)\n",
    "        print(part2)\n",
    "        return (part1*part2)%1337\n",
    "\n",
    "    def mypowmod(self,a,k)-> int:\n",
    "        a = a%1337\n",
    "        res = 1\n",
    "        for i in range(k):\n",
    "            res*=a\n",
    "            res%=1337\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        MOD = 1337\n",
    "        def dfs(i):\n",
    "            if i == -1:\n",
    "                return 1\n",
    "            return quickPow(dfs(i - 1), 10) * quickPow(a, b[i]) % MOD\n",
    "        \n",
    "        def quickPow(x, y):\n",
    "            ans = 1\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    ans = ans * x\n",
    "                x = x * x\n",
    "                y >>= 1\n",
    "            return ans\n",
    "        \n",
    "        a %= MOD\n",
    "        return dfs(len(b) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "\n",
    "        def helper(x, y):\n",
    "            result = 1\n",
    "            while y:\n",
    "                if y & 1:\n",
    "                    result = (result * x) % 1337\n",
    "                x = (x * x) % 1337\n",
    "                y >>= 1\n",
    "            return result\n",
    "        \n",
    "        # def helper(x, y):\n",
    "        #     if y == 0: return 1\n",
    "        #     t = helper(x, y // 2)\n",
    "        #     return t * t if y % 2 == 0 else t * t * x\n",
    "\n",
    "        if not b: return 1\n",
    "        p = b.pop()\n",
    "        return helper(a, p) % 1337 * helper(self.superPow(a, b), 10) % 1337\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def superPow(self, a: int, b: List[int]) -> int:\n",
    "        if len(b) == 0: return 1\n",
    "\n",
    "        base = 1337\n",
    "        def pow(a, k):\n",
    "            res = 1\n",
    "            for i in range(k):\n",
    "                res = res * a\n",
    "                res = res % base\n",
    "            return res\n",
    "\n",
    "\n",
    "\n",
    "        last = b.pop()\n",
    "        part1 = pow(a, last)\n",
    "        part2 = pow(self.superPow(a,b), 10)\n",
    "        return (part1*part2)%base\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
